정점 (그래프 이론)

그래프에서 두 정점이 하나의 모서리로 직접 연결되어 있을 때, 이 두 정점은 서로 인접(adjacent)하다고 말한다. 이때 각 정점은 상대 정점의 인접 정점(adjacent vertex)이 된다. 예를 들어, 정점 A와 B를 잇는 모서리가 존재한다면, A는 B의 인접 정점이며, B 또한 A의 인접 정점이다.

인접 관계는 무향 그래프와 유향 그래프에서 다르게 해석된다. 무향 그래프에서는 모서리에 방향이 없으므로 인접 관계가 항상 상호적이다. 반면 유향 그래프에서는 모서리가 화살표로 표현되는 방향을 가지므로, 정점 A에서 B로 향하는 유향 모서리가 있을 때 A는 B의 선행 정점(predecessor), B는 A의 후행 정점(successor)이 된다. 이 경우, B는 A의 인접 정점이지만, A는 B의 인접 정점이 아닐 수 있다.

인접 정점의 개념은 그래프 탐색이나 네트워크 분석에서 매우 중요하다. 너비 우선 탐색이나 깊이 우선 탐색과 같은 그래프 탐색 알고리즘은 현재 정점의 인접 정점들을 차례로 방문하며 그래프를 순회한다. 또한, 소셜 네트워크에서 친구 관계를 분석할 때, 한 사람의 인접 정점들은 그의 직접적인 친구들에 해당한다.

정점의 차수는 해당 정점에 연결된 모서리의 개수를 의미한다. 무방향 그래프에서 정점 v의 차수는 deg(v)로 표기하며, v에 부착된 모든 모서리의 수를 센다. 방향 그래프에서는 들어오는 모서리의 수를 나타내는 진입차수와 나가는 모서리의 수를 나타내는 진출차수로 구분된다.

차수는 그래프의 구조적 특성을 파악하는 데 중요한 지표가 된다. 예를 들어, 모든 정점의 차수를 합하면 모서리 수의 두 배가 되는데, 이는 각 모서리가 두 정점의 차수에 각각 기여하기 때문이다. 이 관계는 차수 합 공식으로 알려져 있다. 또한, 그래프 내에서 차수가 0인 정점은 고립 정점이며, 차수가 1인 정점은 단말 정점이라고 부른다.

많은 그래프 알고리즘은 정점의 차수 정보를 활용한다. 너비 우선 탐색이나 깊이 우선 탐색과 같은 탐색 알고리즘에서 차수는 인접 정점의 수를 결정하며, 위상 정렬 알고리즘은 진입차수가 0인 정점부터 처리한다. 또한 오일러 경로가 존재하기 위한 필요조건 중 하나는 홀수 차수를 가진 정점의 개수가 0개 또는 2개여야 한다는 것이다.

고립 정점은 그래프에서 차수가 0인 정점을 가리킨다. 즉, 어떤 모서리에도 연결되지 않은, 그래프 내에서 완전히 고립된 정점이다. 이는 그래프의 연결 구조에서 가장 단순한 형태의 정점에 해당한다.

고립 정점의 존재 여부는 그래프의 연결성과 밀접한 관련이 있다. 예를 들어, 하나 이상의 고립 정점을 포함하는 그래프는 연결 그래프가 될 수 없다. 또한 그래프 이론의 여러 알고리즘에서 고립 정점은 처리할 필요가 없거나 초기 단계에서 제외되는 경우가 많다.

다음은 고립 정점과 다른 주요 정점 유형을 비교한 표이다.

고립 정점은 실제 문제 모델링에서도 의미를 가질 수 있다. 예를 들어, 소셜 네트워크에서 친구 관계가 전혀 없는 사용자나, 교통망에서 다른 도로와 연결되지 않은 외딴 지점을 고립 정점으로 표현할 수 있다.

단말 정점은 차수가 1인 정점을 가리킨다. 즉, 다른 정점과 오직 하나의 모서리로만 연결되어 있는 정점이다. 이러한 특성 때문에 단말 정점은 트리 구조에서 잎 노드라고도 불리며, 그래프의 가장자리나 끝부분에 위치하는 경우가 많다.

단말 정점은 그래프의 구조와 속성을 분석하는 데 중요한 단서를 제공한다. 예를 들어, 트리에서는 단말 정점의 개수를 통해 전체 구조의 특성을 유추할 수 있으며, 네트워크 이론에서는 단말 정점이 정보 전달의 종착지나 말단 장치를 나타낼 수 있다. 또한, 그래프 탐색 알고리즘을 수행할 때 단말 정점은 더 이상 탐색할 인접 정점이 없으므로 백트래킹의 지점이 된다.

단말 정점과 유사하지만 구분되는 개념으로 고립 정점이 있다. 고립 정점은 차수가 0인, 즉 어떤 모서리와도 연결되지 않은 정점이다. 반면 단말 정점은 적어도 하나의 연결을 유지하고 있다는 점에서 차이가 있다. 이는 그래프의 연결성과 차수 분포를 이해하는 데 기본이 되는 구분이다.

정점은 그래프에서 경로를 정의하는 핵심 요소이다. 경로란 인접한 변을 통해 연결된 일련의 정점들의 순서열을 말한다. 즉, 한 정점에서 다른 정점으로 이동할 때 거치는 정점과 변의 나열이 경로가 된다. 경로의 시작점과 끝점이 같은 경우를 사이클이라고 부른다.

정점 간의 경로 존재 여부는 그래프 연결성을 결정한다. 어떤 그래프의 모든 정점 쌍 사이에 경로가 존재하면 그 그래프는 연결 그래프이다. 반면, 두 개 이상의 분리된 부분으로 나뉘어 일부 정점 간에 경로가 존재하지 않으면 비연결 그래프가 된다. 이때 서로 경로로 연결된 정점들의 최대 집합을 연결 요소라고 한다.

이러한 경로와 연결성의 개념은 네트워크 분석, 라우팅 알고리즘, 소셜 네트워크 분석 등 다양한 분야에서 그래프의 구조와 효율성을 이해하는 기초가 된다.

부분 그래프는 주어진 그래프에서 일부 정점과 일부 변만을 선택하여 구성한 새로운 그래프이다. 원래 그래프의 정점 집합과 변 집합의 부분집합을 사용하며, 선택된 변의 양 끝점은 반드시 선택된 정점 집합에 포함되어야 한다. 즉, 원본 그래프의 구조와 연결 관계 중 일부만을 취한 것이다.

부분 그래프의 주요 유형으로는 신장 부분 그래프와 유도 부분 그래프가 있다. 신장 부분 그래프는 원본 그래프의 모든 정점을 포함하되, 변은 일부만을 포함하는 그래프이다. 반면, 유도 부분 그래프는 선택된 정점 집합과, 그 정점들 사이에 존재하는 원본 그래프의 모든 변을 포함하는 그래프를 말한다.

부분 그래프의 개념은 그래프 이론에서 복잡한 구조를 더 작고 분석하기 쉬운 단위로 분해하거나, 특정 정점이나 변 집합에 초점을 맞춘 문제를 정의하는 데 유용하게 활용된다.

변은 그래프 이론에서 두 정점 사이의 연결 관계를 나타내는 기본 요소이다. 모서리, 간선, 링크, 아크 등으로도 불린다. 변은 그래프의 구조와 연결성을 정의하는 핵심이며, 방향성의 유무에 따라 무향 변과 유향 변으로 구분된다.

무향 그래프에서 변은 순서가 없는 정점 쌍 {u, v}로 표현되며, 두 정점 u와 v가 서로 인접함을 의미한다. 유향 그래프에서 변은 순서가 있는 정점 쌍 (u, v)로 표현되어, u에서 v로 향하는 방향성을 가진다. 이때 u는 꼬리 정점, v는 머리 정점이라고 부른다. 변은 보통 그래프 G의 변 집합을 E(G)로 표기한다.

변은 여러 특성을 가질 수 있다. 가장 기본적인 것은 가중치를 부여할 수 있다는 점이다. 가중치가 부여된 변을 가진 그래프를 가중 그래프라고 하며, 이는 네트워크 분석, 최단 경로 알고리즘 등에서 거리, 비용, 용량 등의 정보를 표현하는 데 활용된다. 또한, 하나의 변이 동일한 두 정점을 연결하는 경우를 루프라고 하며, 두 정점 사이에 여러 개의 변이 존재할 수 있는 그래프를 다중 그래프라고 한다.

변의 개념은 그래프 표현 방법과도 깊이 연관되어 있다. 인접 행렬은 정점들 사이에 변이 존재하는지를 행렬의 값으로 나타내며, 인접 리스트는 각 정점에 연결된 변의 정보를 리스트로 관리한다. 이러한 표현법은 탐색 알고리즘이나 위상 정렬과 같은 다양한 그래프 알고리즘의 효율성에 직접적인 영향을 미친다.

가중치는 그래프의 변이나 정점에 부여된 수치적 값이다. 이 값은 연결의 비용, 거리, 용량, 시간, 신뢰도 등 다양한 의미를 가질 수 있다. 가중치가 부여된 그래프를 가중 그래프라고 하며, 반대로 가중치가 없는 그래프는 비가중 그래프라고 한다.

가중치는 그래프를 활용한 문제 모델링의 핵심 요소이다. 예를 들어, 도로망에서 도시를 정점, 도로를 변으로 표현할 때, 변에 부여된 가중치는 두 도시 간의 실제 거리나 통행 시간을 나타낼 수 있다. 이는 최단 경로 알고리즘을 적용하는 데 필수적이다. 마찬가지로 통신 네트워크에서는 변의 가중치가 대역폭이나 지연 시간을, 전력망에서는 전선의 저항이나 용량을 의미할 수 있다.

가중치의 적용 대상은 변이 일반적이지만, 정점 자체에도 가중치를 부여할 수 있다. 정점 가중치는 해당 지점의 통행료, 정차 비용, 혹은 중요도 등을 나타내는 데 사용된다. 많은 그래프 알고리즘은 이러한 가중치 정보를 입력받아 최적의 해를 계산한다.

가중치의 개념은 네트워크 이론, 운영 연구, 데이터 과학 등 다양한 분야에서 그래프를 현실 세계의 복잡한 시스템을 표현하는 강력한 도구로 만드는 기반이 된다.

그래프를 컴퓨터에서 처리하거나 시각적으로 표현하기 위해서는 적절한 표현 방법이 필요하다. 그래프 표현은 그래프의 구조, 즉 정점들과 그들을 연결하는 변들의 정보를 효율적으로 저장하고 조작할 수 있는 데이터 구조를 의미한다. 주로 사용되는 표현 방법으로는 인접 행렬과 인접 리스트가 있다.

인접 행렬은 정점의 개수가 n일 때 n x n 크기의 2차원 배열을 사용하는 방식이다. 행렬의 (i, j) 요소는 정점 i와 정점 j 사이에 변이 존재하는지 여부(또는 그 가중치)를 나타낸다. 이 방법은 두 정점 사이의 연결 관계를 상수 시간에 확인할 수 있다는 장점이 있지만, 그래프에 변의 수가 적은 희소 그래프의 경우 많은 메모리 공간을 낭비할 수 있다.

반면, 인접 리스트는 각 정점마다 그 정점에 인접한 정점들의 목록(리스트)을 관리하는 방식이다. 각 정점은 자신과 직접 연결된 이웃 정점들의 정보만 저장한다. 이 방법은 메모리 사용이 효율적이며, 특히 희소 그래프를 표현할 때 유리하다. 하지만 두 정점이 연결되어 있는지 확인하려면 리스트를 순차적으로 탐색해야 할 수 있다는 단점이 있다.

이 외에도 특정 문제에 맞춰 간선 리스트나 인접 배열 등의 변형된 표현 방법이 사용되기도 한다. 표현 방법의 선택은 그래프의 밀도, 수행할 알고리즘의 특성, 그리고 메모리와 시간 효율성 사이의 트레이드오프를 고려하여 결정된다.

그래프에서 정점은 탐색 알고리즘의 핵심 탐색 대상이 된다. 대표적인 탐색 알고리즘인 깊이 우선 탐색과 너비 우선 탐색은 모두 특정 정점에서 시작하여, 그 정점과 인접한 다른 정점들을 체계적으로 방문하는 과정을 반복한다. 이 과정에서 각 정점은 방문 여부를 기록하는 상태 정보를 가지며, 알고리즘의 진행을 위한 자료 구조에 저장되거나 추출된다.

탐색 알고리즘에서 정점의 처리 순서는 알고리즘의 목적에 따라 결정된다. 깊이 우선 탐색은 한 정점에서 시작해 가능한 깊숙이 들어가 탐색을 진행하기 때문에 스택 자료 구조를 사용하는 반면, 너비 우선 탐색은 시작 정점과 가까운 정점들을 우선적으로 방문하기 위해 큐를 사용한다. 이는 그래프의 연결성을 확인하거나 사이클을 발견하는 등 다양한 문제 해결의 기초가 된다.

이러한 탐색 알고리즘은 더 복잡한 알고리즘의 구성 요소로 널리 쓰인다. 예를 들어, 다익스트라 알고리즘이나 A* 알고리즘과 같은 최단 경로 알고리즘은 너비 우선 탐색의 개념을 확장하여 각 정점까지의 거리 또는 비용을 누적해 가며 최적의 경로를 찾는다. 또한, 위상 정렬은 방향성 비순환 그래프의 정점들을 선후 관계에 따라 나열하는데, 이는 내부적으로 깊이 우선 탐색을 기반으로 한다.

최단 경로 알고리즘은 그래프에서 한 정점에서 다른 정점까지 도달하는 데 필요한 비용이 가장 적은 경로를 찾는 알고리즘이다. 여기서 비용은 일반적으로 경로를 구성하는 모든 변의 가중치 합을 의미하며, 가중치가 없는 그래프에서는 변의 개수로 간주한다. 이러한 알고리즘은 네트워크 라우팅, 내비게이션 시스템, 물류 경로 최적화 등 다양한 분야에서 핵심적으로 활용된다.

대표적인 최단 경로 알고리즘으로는 다익스트라 알고리즘과 벨만-포드 알고리즘, 플로이드-워셜 알고리즘이 있다. 각 알고리즘은 처리할 수 있는 그래프의 특성과 계산 복잡도에서 차이를 보인다. 다익스트라 알고리즘은 음의 가중치를 허용하지 않는 그래프에서 단일 출발점 최단 경로를 효율적으로 구하는 반면, 벨만-포드 알고리즘은 음의 가중치를 처리할 수 있고 음수 사이클의 존재 여부도 판별할 수 있다.

이들 알고리즘의 핵심 동작은 각 정점까지의 현재 알려진 최단 거리 추정값을 유지하고, 이를 반복적으로 개선해 나가는 과정이다. 알고리즘이 진행되면서 정점은 '방문 완료' 또는 '미방문' 상태로 구분되며, 방문 완료된 정점까지의 거리는 최단 거리로 확정된다. 이 과정은 출발점 정점에서 시작하여 목표 정점이 방문 완료 상태가 되거나, 모든 가능한 정점을 처리할 때까지 계속된다.

위상 정렬은 방향 그래프의 모든 정점을 방향성을 거스르지 않는 순서로 나열하는 알고리즘 기법이다. 주로 순환이 없는 방향 그래프, 즉 DAG에 적용되며, 작업 간의 선후 관계가 명확한 스케줄링 문제나 의존성 해결에 널리 사용된다.

위상 정렬의 핵심은 진입 차수가 0인 정점, 즉 자신에게 들어오는 모서리가 없는 정점부터 순서대로 제거해 나가는 것이다. 일반적인 알고리즘 과정은 다음과 같다.

이 과정에서 모든 정점이 정렬되면 위상 정렬이 완성된 것이며, 만약 아직 처리되지 않은 정점이 남아 있다면 그래프에 순환이 존재한다는 것을 의미한다. 위상 정렬의 결과는 반드시 유일하지 않으며, 여러 가지 유효한 순서가 존재할 수 있다. 이 알고리즘은 컴파일러의 코드 최적화, 프로젝트 관리의 임계 경로 분석, 패키지 관리자의 의존성 설치 순서 결정 등 다양한 분야에서 활용된다.